As today's networks become increasingly complex and are comprised of equipment from multiple vendors, exhaustively testing all possible behaviors of the network becomes infeasible. The analysis of real-time behavior only increases this complexity. A number of techniques have been proposed or suggested for testing real-time behavior of complex systems.
Real-time model checking techniques, for example, assume that a specification of the system is given as a (concurrent set of) timed automata. Model checking tools then exhaustively analyze this specification against desired properties expressed in real-time variants of temporal logic. While model checking has been successful in identifying errors in critical portions of systems, it suffers from two challenges. First, model checking does not scale to large-scale systems because the size of the state space becomes intractable. In addition, model checking identifies errors in the specification of the system rather than in the actual system implementation. These challenges are further exacerbated for analysis of real-time systems.
In conformance testing techniques, the system implementation under test is given as a black box, in which the interface to the black box is known, inputs can be sent to the black box, and the outputs of the black box are observable. A modeling formalism is chosen such that the implementation can be assumed to be an (unknown) model in this formalism, and the specification of the system can be described as a model in this formalism. Conformance testing then generates a comprehensive suite of test cases to validate that the implementation satisfies the specification. In particular, the test cases correspond to sequences of inputs sent to the implementation, and the resulting outputs are compared to those expected by the specification as per a formally specified conformance relation. The test case generation can be done prior to testing (offline), or during testing (online/on-the-fly).
Passive monitoring techniques observe network equipment while it is running in the field. For certain applications, such as network management and intrusion detection for security, passive monitoring is, in fact, the only available methodology for validating the system's behavior. More generally, passive monitoring can be used to complement and augment functional testing and fault detection efforts that take place during the product/software development lifecycle.
A key challenge of passive monitoring is that observations of the system are necessarily obtained mid-stream, from an unknown state during the middle of the execution of the system. Generally, the mid-stream nature of passive testing places a limitation on the extent to which a property can be tested. For an arbitrary correctness property, while any rejected implementation is definitively faulty, all faulty implementations may not necessarily be detectable on the basis of their mid-stream observations. Passive monitoring techniques cannot make assumptions about the previous (unobserved) history of the system during its execution. Furthermore, passive monitoring techniques cannot influence the execution of the system by providing particular inputs to the system.
A need therefore exists for improved passive monitoring techniques that can observe the mid-stream behavior of systems during their execution in arbitrary environments. A further need exists for passive monitoring techniques that address those properties for which complete fault coverage can be achieved through passive testing.